package com.lbc.sort;

import java.util.Arrays;

public class InsertSort {
    // 插入排序 O(n^2)：把后面无序区的第一个数 -> 有序区中合适的位置
    // 类似与斗地主时的齐牌类似，不过牌是直接插入，算法是往前挪
    public static void main(String[] args) {
        int arr [] = {3, 9, -1, 10, -2};
        System.out.println("排序前的数组为：" + Arrays.toString(arr));
        insertSort(arr);
        System.out.println("排序后的数组为：" + Arrays.toString(arr));
        // 这个测80000个数字也就两三秒种吧
    }

    public static void insertSort(int [] arr) {
        int temp;
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                if (arr[j - 1] < arr[j]) {
                    break;
                }
                temp = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = temp;
            }
        }
    }
}
